Basic stacks and arrays are data structure and data storage concepts that are commonly known in the computer arts. Among other things, stacks are commonly used as an area in storage that stores temporary register information
In a gate array Application Specific Integrated Circuit (herein referred to as an “ASIC”), stacks can be implemented as either banks of registers or an embedded memory array to store the stack values. Each of these approaches is problematic.
If a stack is implemented using banks of registers in a gate array ASIC, each register comprised of a given number of flip-flop storage elements typically contains one stack value. The registers are generally connected together in such a way as to allow their data to be shifted down to the register below them or moved to the top register location, as directed by the associated control logic. With this approach, an insertion of a new value or a promotion of an existing value to the top of the stack is generally accomplished in one clock cycle, with all registers taking on their new values following the clock edge. However, as the size of the register values grows and/or as the number of registers increases, the efficiency of the ASIC real estate, e.g. size of the gate array, used decreases.
Although using a typical memory array, rather than registers, avoids the real estate problems posed by register use, the memory array provides access to only one value at a time per data port, wherein a typical memory array has approximately one or two access ports. Depending on the number of values in the array, a considerable number of memory accesses may be required to move each value to the next location in order to insert a new value at the top location.
For example, to insert a fourth item D into an array where location 1 is the top of the stack and the array contains three items, namely, A, B and C, at locations 1, 2 and 3 respectively, the following actions occur. Item A is read and rewritten to location 2 Item B is read and rewritten to location 3. Item C is read and rewritten to location 4. Item D is written to location 1. Thus, implementing a stack as an array produces significant overhead when performing stack operations such as inserting and removing items from the stack.